import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

public class FPTree extends AssoRuleMining {
	// FP tree node
	public class FPTreeNode {
		private ItemPrefixSubtreeNode node = null;
		private LinkedList<FPTreeNode> childs = null;

		public FPTreeNode() {
			childs = new LinkedList<FPTreeNode>();
		}

		public FPTreeNode(ItemPrefixSubtreeNode newNode) {
			node = newNode;
			childs = new LinkedList<FPTreeNode>();
		}

		public void InsertTransaction(Short[] dataArray, int minSupport) {
			SortItems(dataArray);
			FPTreeNode startNode = rootNode;
			InsertItems(dataArray, startNode, 0, minSupport);
		}

		public void InsertTransWithoutSort(Short[] dataArray, int minSupport) {
			FPTreeNode startNode = rootNode;
			InsertItems(dataArray, startNode, 0, minSupport);
		}

		public void InsertItems(Short[] dataArray, FPTreeNode startNode,
				int indexList, int support) {
			boolean IsFound = false;
			int index = -1;
			for (int i = 0; i < startNode.childs.size(); i++) {
				if (dataArray[indexList] == startNode.childs.get(i).node.itemID) {
					IsFound = true;
					index = i;
					break;
				}
			}

			if (IsFound) {
				FPTreeNode t = startNode.childs.get(index);
				t.node.support++;
				startNode.childs.set(index, t);
				indexList++;
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {
					InsertItems(dataArray, t, indexList, support);
				}
			} else {
				ItemPrefixSubtreeNode t = new ItemPrefixSubtreeNode(
						dataArray[indexList], 1, startNode.node);
				FPTreeNode insertNode = new FPTreeNode(t);
				startNode.childs.addLast(insertNode);

				// Link header Table and same value
				int indexHeader = findIndexHeaderTable(dataArray[indexList]);
				if (indexHeader != -1) {
					HeaderTable header = headerTableFinal[indexHeader];
					// First item of type
					if (header.nodeLink == null) {
						header.nodeLink = insertNode.node;
					} else {
						ItemPrefixSubtreeNode ref = header.nodeLink;
						while (ref.refSameItem != null) {
							ref = ref.refSameItem;
						}
						ref.refSameItem = insertNode.node;
					}
				}

				indexList++;
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {
					InsertItems(dataArray, insertNode, indexList, support);

				}
			}
		}
	}

	public int findIndexHeaderTable(Short item) {
		for (int i = 0; i < headerTableFinal.length; i++) {
			if (headerTableFinal[i].itemID == item)
				return i;
		}
		return -1;
	}

	public void SortItems(Short[] dataArray2) {
		Arrays.parallelSort(dataArray2, new Comparator<Short>() {
			@Override
			public int compare(Short o1, Short o2) {
				int value = supportCountHash.get(o2) - supportCountHash.get(o1);
				if (value != 0)
					return value;
				else
					return o1 - o2;
			}
		});
	}

	// header table
	public class HeaderTable {
		protected short itemID;
		private int supportCount;
		private ItemPrefixSubtreeNode nodeLink = null;

		public HeaderTable(short colNum, int support) {
			supportCount = support;
			itemID = colNum;
		}

		public int getSupportCount() {
			return supportCount;
		}

		public short getItemID() {
			return itemID;
		}
	}

	public void CompleteHeaderTable() {
		boolean swapped = true;
		int j = 0;
		HeaderTable tmp;
		// Update support
		for (int i = 0; i < headerTable.size(); i++) {
			tmp = headerTable.get(i);
			tmp.supportCount = supportCountHash.get(tmp.itemID);
			
			//if(supportCountHash.get(tmp.itemID) >= 2) {
				headerTable.set(i, tmp);			
			//}
			//else {
				//headerTable.remove(i);
			//}
			
		}
		for(int i = 0; i< headerTable.size(); i++) {
			if(headerTable.get(i).supportCount < 2) {
				headerTable.remove(i);
				i--;
			}
		}
		// parallel sort
		headerTableFinal = headerTable.toArray(new HeaderTable[headerTable
				.size()]);
		Arrays.parallelSort(headerTableFinal, new Comparator<HeaderTable>() {
			@Override
			public int compare(HeaderTable o1, HeaderTable o2) {
				int value = o2.getSupportCount() - o1.getSupportCount();
				if (value != 0)
					return value;
				else
					return o1.getItemID() - o2.getItemID();
			}

		});
		//System.out.println("item: "+headerTableFinal[headerTableFinal.length -1 ].itemID);
		//System.out.println("supp: "+headerTableFinal[headerTableFinal.length -1 ].supportCount);

	}

	// Item prefix subtree node
	public class ItemPrefixSubtreeNode {
		protected short itemID;
		private int support;
		private ItemPrefixSubtreeNode parent = null;
		private ItemPrefixSubtreeNode refSameItem = null;

		public ItemPrefixSubtreeNode() {

		}

		public ItemPrefixSubtreeNode(short name, int itemCount,
				ItemPrefixSubtreeNode backRef) {
			itemID = name;
			support = itemCount;
			parent = backRef;
		}

		public ItemPrefixSubtreeNode(short name, int itemCount) {
			itemID = name;
			support = itemCount;
			parent = null;
		}
	}

	// update support hash
	public void updateSupportCountHash(short item) {
		if (supportCountHash.containsKey(item)) {
			supportCountHash.put(item, supportCountHash.get(item) + 1);
		} else {
			supportCountHash.put(item, 1);
			// Add items to headerTable
			HeaderTable itemType = new HeaderTable(item, 0);
			headerTable.addLast(itemType);
		}

	}

	// get total rows in file
	public int getRows(String fileName) {
		int numRows = 0;
		File file = new File(fileName);
		BufferedReader reader = null;

		try {
			reader = new BufferedReader(new FileReader(file));
			String line = reader.readLine();
			while (line != null) {
				numRows++;
				line = reader.readLine();
			}
			reader.close();
		} catch (Exception e) {

		}

		return numRows;
	}

	// read file to data array to reduce run time
	public void readFileToDataArray() {
		// read input from file
		File file = new File("input1.txt");
		BufferedReader reader = null;
		int numRows = getRows("input1.txt");
		dataArray = new Short[numRows][];

		try {
			reader = new BufferedReader(new FileReader(file));
			int rowIndex = 0;
			String current;
			current = reader.readLine();
			while (current != null) {
				StringTokenizer line = new StringTokenizer(current);
				dataArray[rowIndex] = new Short[line.countTokens()];
				int colIndex = 0;
				while (line.hasMoreElements()) {
					dataArray[rowIndex][colIndex] = Short.parseShort(line
							.nextElement().toString());
					colIndex++;
				}
				rowIndex++;
				current = reader.readLine();
			}
			reader.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public FPTree() {
		rootNode = new FPTreeNode();
		headerTable = new LinkedList<HeaderTable>();
	}

	// fp tree root
	protected FPTreeNode rootNode;
	// protected CondPatBase listCPB = new CondPatBase();
	protected LinkedList<CondPattern> listParent = null;
	// header table
	protected LinkedList<HeaderTable> headerTable = null;
	// support count hash
	protected HeaderTable[] headerTableFinal;
	protected HashMap<Short, Integer> supportCountHash = new HashMap();
	// data array to store input data read from file
	protected Short[][] dataArray = null;

	protected LinkedList<CondPatternBase> cpbTable = new LinkedList<CondPatternBase>();

	public class CondPattern extends Pattern {
		// private LinkedList<ItemPrefixSubtreeNode> items;
		// protected int support;

		public CondPattern() {
			items = new LinkedList<ItemPrefixSubtreeNode>();
			support = 0;
		}

		public void insertPrefix(ItemPrefixSubtreeNode node) {
			ItemPrefixSubtreeNode nodetmp = node;
			while (nodetmp != null) {
				if (nodetmp.parent != null) {
					ItemPrefixSubtreeNode tmp = nodetmp.parent;
					if (tmp != null) {
						items.addFirst(tmp);
					}
				}
				nodetmp = nodetmp.parent;
			}
		}
	}

	public class CondPatternBase {
		protected short itemID;
		LinkedList<CondPattern> prefixList;

		public CondPatternBase() {
			prefixList = new LinkedList<CondPattern>();
		}

		public CondPatternBase(ItemPrefixSubtreeNode node) {
			itemID = node.itemID;
			prefixList = new LinkedList<CondPattern>();
		}

		public void insertCondPatternBase(ItemPrefixSubtreeNode node) {
			ItemPrefixSubtreeNode tmp = node;
			while (tmp != null) {
				CondPattern nodetmp = new CondPattern();
				nodetmp.insertPrefix(tmp);
				nodetmp.support = tmp.support;
				if (!nodetmp.items.isEmpty()) {
					prefixList.add(nodetmp);
				}
				tmp = tmp.refSameItem;
			}
		}

	}

	public void generateCPB() {
		CondPatternBase listCPB = null;
		long start = System.currentTimeMillis();
		for (int i = headerTableFinal.length - 1; i > 0; i--) {
			if (headerTableFinal[i].nodeLink != null) {
				listCPB = new CondPatternBase();
				listCPB.insertCondPatternBase(headerTableFinal[i].nodeLink);
				listCPB.itemID = headerTableFinal[i].itemID;
				// listCPB.listparent.
				cpbTable.add(listCPB);
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("time of CPB: " + (long) ((end - start)));

		for (CondPatternBase tmp : cpbTable) {
			System.out.println(tmp.itemID);
			for (CondPattern tmp1 : tmp.prefixList) {
				System.out.print("{");
				for (ItemPrefixSubtreeNode t : tmp1.items) {
					System.out.print(t.itemID + " ");
				}
				System.out.print("sup: " + tmp1.support + "}");
			}
			System.out.println();
		}
	}

	public CondPatternBase generateCondPatternBase(HeaderTable item) {
		CondPatternBase condPattern = null;

		if (item.nodeLink != null) {
			condPattern = new CondPatternBase();
			condPattern.insertCondPatternBase(item.nodeLink);
			condPattern.itemID = item.itemID;
		}

		return condPattern;
	}

	public boolean containSinglePath() {
		FPTreeNode tmpNode = rootNode;
		boolean flag = true;

		while (!tmpNode.childs.isEmpty()) {
			if (tmpNode.childs.size() > 1) {
				flag = false;
				break;
			}
			tmpNode = tmpNode.childs.get(0);
		}
		return flag;
	}

	public void miningFrequentPattern() {
		long start = System.currentTimeMillis();
		fpGrowth(this, null);
		long end = System.currentTimeMillis();
		System.out.println("time of mining frequent pattern: " + (end - start));
		
		start = System.currentTimeMillis();
		writeFrequentPatternToFile();
		end = System.currentTimeMillis();
		System.out.println("time of write down frequent pattern: " + (end - start));


		
		 System.out.println("frequent patterns"); for (Pattern pattern :
		 frequentPatterns) { System.out.print("{"); for (ItemPrefixSubtreeNode
		 item : pattern.items) { System.out.print(item.itemID + ", "); }
		 System.out.print("sup: " + pattern.support + "}");
		  System.out.println(); }
		 
	}
	
	public int minSupBeta(LinkedList<ItemPrefixSubtreeNode> beta){
		int min = beta.get(0).support;
		for(int i= 1; i< beta.size();i++){
			if(beta.get(i).support<min)
			{
				min = beta.get(i).support;
			}
		}
		return min;
	}

	public void fpGrowth(FPTree tree, LinkedList<ItemPrefixSubtreeNode> alpha) {
		if (tree.containSinglePath()) {
			LinkedList<LinkedList<ItemPrefixSubtreeNode>> combineNodeList = combineNodeInPath(tree.rootNode);
			for (LinkedList<ItemPrefixSubtreeNode> beta : combineNodeList) {
				Pattern pattern = new Pattern();
				pattern.items = generatePartern(beta, alpha);
				//System.out.println("tree "+tree.rootNode.childs.get(0).node.support);
				//System.out.println("length "+(tree.headerTableFinal.length - 1));
				
				//System.out.println("item: "+tree.headerTableFinal[tree.headerTableFinal.length -1 ].itemID);
				//System.out.println("supp: "+tree.headerTableFinal[tree.headerTableFinal.length -1 ].supportCount);

				pattern.support = minSupBeta(beta);
				frequentPatterns.add(pattern);
			}
		} else {
			for (HeaderTable item : tree.headerTableFinal) {
				ItemPrefixSubtreeNode node = new ItemPrefixSubtreeNode(
						item.itemID, item.supportCount);
				LinkedList<ItemPrefixSubtreeNode> listA = new LinkedList<ItemPrefixSubtreeNode>();
				listA.add(node);
				Pattern pattern = new Pattern();
				pattern.items = generatePartern(listA, alpha);
				pattern.support = item.supportCount;
				frequentPatterns.add(pattern);
				CondPatternBase betaCondPatternBase = tree
						.generateCondPatternBase(item);

				FPTree treeBeta = new FPTree();
				if (betaCondPatternBase != null) {
					treeBeta.generateFromCondPatternBase(betaCondPatternBase);
				}
				if (!treeBeta.isNull())
					fpGrowth(treeBeta, pattern.items);
			}
		}
	}

	public class Pattern {
		protected LinkedList<ItemPrefixSubtreeNode> items;
		protected int support;

		public Pattern() {
			items = new LinkedList<ItemPrefixSubtreeNode>();
			support = 0;
		}
	}

	protected LinkedList<Pattern> frequentPatterns = new LinkedList<FPTree.Pattern>();

	public LinkedList<LinkedList<ItemPrefixSubtreeNode>> combineNodeInPath(
			FPTreeNode root) {
		Pattern partern = new Pattern();
		FPTreeNode tmp = root;

		while (!tmp.childs.isEmpty()) {
			partern.items.add(tmp.childs.get(0).node);
			tmp = tmp.childs.get(0);
		}

		LinkedList<LinkedList<ItemPrefixSubtreeNode>> result = getSubSetList(partern.items);
		result.removeLast();
		return result;
	}

	public LinkedList<LinkedList<ItemPrefixSubtreeNode>> getSubSetList(
			LinkedList<ItemPrefixSubtreeNode> list) {
		LinkedList<LinkedList<ItemPrefixSubtreeNode>> result = new LinkedList<LinkedList<ItemPrefixSubtreeNode>>();

		if (list.isEmpty()) {
			result.add(new LinkedList<FPTree.ItemPrefixSubtreeNode>());
			return result;
		}

		ItemPrefixSubtreeNode head = list.remove(0);

		for (LinkedList<ItemPrefixSubtreeNode> subSet : getSubSetList(list)) {
			LinkedList<ItemPrefixSubtreeNode> tmp = new LinkedList<FPTree.ItemPrefixSubtreeNode>();
			tmp.add(head);
			tmp.addAll(subSet);
			result.add(tmp);
			result.add(subSet);
		}
		return result;
	}

	public LinkedList<ItemPrefixSubtreeNode> generatePartern(
			LinkedList<ItemPrefixSubtreeNode> list1,
			LinkedList<ItemPrefixSubtreeNode> list2) {
		if (list1 == null && list2 == null)
			return null;
		if (list1 != null && list2 == null)
			return list1;
		if (list2 != null && list1 == null)
			return list2;
		list1.addAll(list2);
		return list1;
	}

	public void generate() {

		long start = System.currentTimeMillis();

		readFileToDataArray();

		for (int i = 0; i < dataArray.length; i++) {
			for (int j = 0; j < dataArray[i].length; j++) {
				updateSupportCountHash(dataArray[i][j]);
			}
		}

		long end = System.currentTimeMillis();

		System.out.println("time of read file: " + (long) ((end - start)));

		start = System.currentTimeMillis();
		CompleteHeaderTable();
		end = System.currentTimeMillis();
		System.out.println("time of sort header table: "
				+ (long) ((end - start)));

		// add node to fp tree
		start = System.currentTimeMillis();

		for (int i = 0; i < dataArray.length; i++) {
			rootNode.InsertTransaction(dataArray[i], 2);
		}

		end = System.currentTimeMillis();
		System.out.println("time of fp generate: " + (long) ((end - start)));
	}

	public void generateFromCondPatternBase(CondPatternBase condPatternBase) {
		Short[][] data;
		int numRows = 0;
		int currentRow = 0;

		for (CondPattern prefix : condPatternBase.prefixList) {
			numRows += prefix.support;
		}

		data = new Short[numRows][];

		for (CondPattern prefix : condPatternBase.prefixList) {
			for (int time = 0; time < prefix.support; time++) {
				int currentCol = 0;
				data[currentRow] = new Short[prefix.items.size()];
				for (ItemPrefixSubtreeNode item : prefix.items) {
					data[currentRow][currentCol] = item.itemID;
					currentCol++;
				}
				currentRow++;
			}
		}
		// System.out.println(data[0].length);
		generate(data);

	}

	public void generate(Short[][] data) {
		// read input from data array
		// System.out.println(data[0].length);
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[i].length; j++) {
				updateSupportCountHash(data[i][j]);
			}
		}

		// sort header table
		CompleteHeaderTable();

		// build fp tree with it's header table (headerTableFinal)
		for (int i = 0; i < data.length; i++) {
			rootNode.InsertTransWithoutSort(data[i], 2);
		}
	}

	public boolean isNull() {
		if (rootNode.childs.isEmpty())
			return true;
		return false;
	}

	public void writeFrequentPatternToFile() {
		try {
			StringBuilder content = new StringBuilder();
			
			File file = new File("freq_pattern.txt");

			if (!file.exists()) {
				file.createNewFile();
			}

			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			BufferedWriter bw = new BufferedWriter(fw);

			
			for (Pattern pattern : frequentPatterns) {
				
				content.append("{");
				for (ItemPrefixSubtreeNode item : pattern.items) {
					content.append(Short.toString(item.itemID) + ", ");
				}
				content.append("sup: " + Integer.toString(pattern.support) + "}");
				content.append("\n");
				if(content.length() > 1024) {
					String tmp = content.toString();
					content = new StringBuilder();
					bw.write(tmp);
				}
				//System.out.println(content);
			}
			String tmp = content.toString();
			bw.write(tmp);
			bw.close();

			System.out.println("done");
		} catch (IOException e) {

		}

	}
}
